package chapter04_RecursionAndDynamic;

import java.util.Arrays;

/**
 * 描述：
 * 给定一个数组arr，返回数组的最长递增子序列
 *
 * @author hl
 * @date 2021/6/6 10:07
 */
public class GetLIS {
    public static void main(String[] args) {
        GetLIS main = new GetLIS();
        int[] arr = {2, 1, 5, 3, 6, 4, 8, 9, 7};
        int[] res = main.list1(arr);
        int[] res2 = main.list2(arr);
        System.out.println(Arrays.toString(res));
        System.out.println(Arrays.toString(res2));
    }
    public int[] list2(int[] arr){
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int[] dp = getDp2(arr);
        return generateLIS(arr, dp);
    }

    /**
     * 将求dp数组的时间复杂度降低到O(NlogN)，如果将第二层循环查找0~i-1中最大的递增数组长度变为二分查找，
     * 那么时间复杂度就可以降低到O(NlogN)，如果通过二分查找来生成dp数组呢？
     * 需要构建一个ends数组记录递增长度的子序列的最小结尾，end[b]=c表示长度为b+1的递增序列的最小结尾值为c
     * 初始时ends[0]=arr[0]，表示长度为1的递增子序列的结尾最小值为arr[0],则dp[0]=1，
     * 在遍历的过程中更新ends数组，然后通过ends数组求得dp
     * ends必然是一个递增的数组，在更新dp[i]，用二分查找ends[0...i-1]范围中最左边大于或等于arr[i]的元素，
     * 如果存在则在最左边大于或等于arr[i]的元素下标为j，那么更新ends[j]=arr[i]表示长度为j+1的序列的最小值为arr[i],dp[i]=j+1
     * @param arr
     * @return
     */
    private int[] getDp2(int[] arr) {
        int n = arr.length, right = 0, l = 0, r = 0, mid = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        int[] ends = new int[n];
        ends[0] = arr[0];
        for (int i = 1; i < n; i++) {
            l = 0;
            r = right;
            while(l <= r){
                mid = l + ((r - l) >> 1);
                if (ends[mid] < arr[i]) {
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            right = Math.max(right, l);
            ends[l] = arr[i];
            dp[i] = l + 1;
        }
        return dp;
    }
    private int[] getDp3(int[] arr) {
        int n = arr.length, right = 0;
        int[] dp = new int[n];
        int[] ends = new int[n];
        ends[0] = arr[0];
        int ei = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            ei = getLeftMost(ends, 0, right, arr[i]);
            right = Math.max(right, ei);
            ends[ei] = arr[i];
            dp[i] = ei + 1;
        }
        return dp;
    }

    private int getLeftMost(int[] ends, int l, int r, int target) {
        if (l > r) {
            return l;
        }
        int mid = l + ((r - l) >> 1);
        int index = 0;
        if (ends[mid] < target) {
            index = getLeftMost(ends, mid + 1, r, target);
        }else if (ends[mid] >= target) {
            index = getLeftMost(ends, l, mid - 1, target);
        }
        return index;
    }


    /**
     * 动态规划，时间复杂度O(N^2)，因为求dp数组的时间复杂度为O(N^2),所以整体的时间复杂度为O(N^2)
     * @param arr
     * @return
     */
    public int[] list1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int[] dp = getDp1(arr);
        return generateLIS(arr, dp);
    }

    /**
     * 有了dp数组，可以找到最长递增子序列的结尾的下标，然后可以通过dp数组反推出每一步的决策，从而找到整个递增序列
     * 最长递增子序列是以j结尾，决策的过程是：
     * 1）从j开始向左遍历，如果找到小于j的数i，并且dp[i] = dp[j] - 1，那么i就是序列中倒数第二个值
     *
     * @param arr
     * @param dp
     * @return
     */
    private int[] generateLIS(int[] arr, int[] dp) {
        int index = 0, n = arr.length, len = dp[0];
        for (int i = 1; i < n; i++) {
            if (len < dp[i]) {
                index = i;
                len = dp[i];
            }
        }
        int[] res = new int[len];
        res[--len] = arr[index];
        for (int i = index; i >= 0; i--) {
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
                res[--len] = arr[i];
                index = i;
            }
        }
        return res;
    }

    /**
     * 生成一个与arr等长的数组dp，dp[i]代表以i结尾的数组arr[0...i]中最大的递增子序列，
     * dp[0]=1，dp[i]的取值需要遍历arr中0~i-1的值，找到比arr[i]小并且dp[j]最大的值，在他基础上+1
     * dp[i] = max{dp[j] + 1(0<=j<i,arr[j] < arr[i])}
     * dp[i]的值依赖于前面以arr[j](arr[j] < arr[i])结尾的最大递增子序列，如果找不到比arr[i]小的值，那么dp[i]=1
     *
     * @param arr
     * @return
     */
    private int[] getDp1(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }
}
